package Algorithm.dynamicProgramming.introduct;

/**
 * 198. 打家劫舍 https://leetcode.cn/problems/house-robber
 * 题目简述：一个屋子序列，每个屋子有个价值，不能连续偷两个屋子，求能偷到的最大价值
 */
public class Rob {

    /**
     * 注意不能直接用简单的偷奇数或偷偶数来比较，因为有可能最大价值是半段奇数加半段偶数的
     * 思路：动态规划。屋子直接从0开始编号
     * 1. 定义dp：dp[i][0]为不偷第i个屋子的最大价值和，dp[i][1]为偷第i个屋子的最大价值和
     * 2. 状态转移公式：dp[i][0] = max(dp[i-1][0], dp[i-1][1], dp[i-1][1])
     *               dp[i][1] = dp[i-1][0] + values[i]
     * 3. 初始化：dp[0][0] = 0; dp[0][1] = values[0]
     */
    public int rob(int[] nums) {
        int[][] dp = new int[nums.length][2];
        dp[0][0] = 0;dp[0][1] = nums[0];
        for (int i = 1;i < nums.length;i++) {
            dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1]);
            dp[i][1] = dp[i-1][0] +nums[i];
        }
        return Math.max(dp[nums.length-1][0], dp[nums.length-1][1]);
    }
}
